package main

//128. 最长连续序列
func main() {
	nums := []int{100, 4, 200, 1, 3, 2}
	res := longestConsecutive(nums)
	println(res)
}

func longestConsecutive1(nums []int) int { // 2025.02.23 练习
	numMap := make(map[int]bool)

	for _, n := range nums {
		numMap[n] = true
	}

	maxLen := 0
	for n, _ := range numMap {
		if numMap[n+1] {
			continue
		}
		// 已经到临界或者已经不和下一位连续了，往回找
		ptr := n - 1
		for numMap[ptr] {
			ptr--
		}
		currMax := n - ptr

		if currMax > maxLen {
			maxLen = currMax
		}
	}

	return maxLen
}

func longestConsecutive(nums []int) int {
	numMap := make(map[int]bool)
	for _, n := range nums {
		numMap[n] = true
	}

	maxLen := 0
	for n, _ := range numMap {
		if _, has := numMap[n-1]; has {
			continue
		}

		currLen := 1
		currNum := n
		for numMap[currNum+1] {
			currLen++
			currNum++
		}

		if currLen > maxLen {
			maxLen = currLen
		}
	}
	return maxLen
}

// 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
//
//请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
//
//示例 1：
//
//输入：nums = [100,4,200,1,3,2]
//输出：4
//解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
//示例 2：
//
//输入：nums = [0,3,7,2,5,8,4,6,0,1]
//输出：9
//
//
//提示：
//
//0 <= nums.length <= 105
//-109 <= nums[i] <= 109
